package com.hellohu.dp;

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class ClimbingStairs {

    @Test
    public void test() {
        Assertions.assertThat(divideSolution(10)).isEqualTo(89);
        Assertions.assertThat(memoSolution(10, new int[11])).isEqualTo(89);
        Assertions.assertThat(dpSolution(10)).isEqualTo(89);
    }

    /**
     * 分治
     * 
     * @param n
     * @return
     */
    public int divideSolution(int n) {
        if (n <= 1) {
            return 1;
        }
        return divideSolution(n - 2) + divideSolution(n - 1);
    }

    /**
     * 备忘录
     * 
     * @param n
     * @param memo
     * @return
     */
    public int memoSolution(int n, int[] memo) {
        if (n <= 1) {
            return 1;
        }
        if (memo[n] == 0) {
            memo[n] = divideSolution(n - 2) + divideSolution(n - 1);
        }
        return memo[n];
    }

    /**
     * @param n
     * @return
     */
    public int dpSolution(int n) {
        int pre = 1, prepre = 1, cur = 1;
        for (int i = 2; i <= n; ++i) {
            cur = pre + prepre;
            prepre = pre;
            pre = cur;
        }
        return cur;
    }
}
